package practice;

public class 堆排序 {
    public static void main(String[] args) {
        int[] arr = {50,10,90,30,70,40,80,60,20};
        System.out.println("排序之前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + " ");
        }

        heapSort(arr);
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + " ");
        }
    }

    /**
     * 堆排序
     */
     private static void heapSort(int[] arr) {
         // 将待排序的序列构造成一个大顶堆
         for (int i = arr.length/2; i >= 0; i--) {
            heapAdjust(arr,i,arr.length);
         }
     }

     private static void heapAdjust(int[] arr, int i, int n) {
         int child;
         int father;
         for (father = arr[i]; leftChild(i) < n; i = child) {
             child = leftChild(i);

             if (child != n-1 && arr[child] < arr[child + 1]) {
                 child++;
             }
             if (father < arr[child]) {
                 arr[i] = arr[child];
             }else {
                 break;
             }
         }
         arr[i] = father;
     }

     private static int leftChild(int i) {
         return 2*i + 1;
     }
}
